{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize the Maximum Difference of Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeMax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化数对的最大差值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>p</code>&nbsp;。请你从&nbsp;<code>nums</code>&nbsp;中找到&nbsp;<code>p</code> 个下标对，每个下标对对应数值取差值，你需要使得这 <code>p</code> 个差值的&nbsp;<strong>最大值</strong>&nbsp;<strong>最小</strong>。同时，你需要确保每个下标在这&nbsp;<code>p</code>&nbsp;个下标对中最多出现一次。</p>\n",
    "\n",
    "<p>对于一个下标对&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code>&nbsp;，这一对的差值为&nbsp;<code>|nums[i] - nums[j]|</code>&nbsp;，其中&nbsp;<code>|x|</code>&nbsp;表示 <code>x</code>&nbsp;的 <strong>绝对值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <code>p</code>&nbsp;个下标对对应数值 <strong>最大差值</strong>&nbsp;的 <strong>最小值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [10,1,2,7,1,3], p = 2\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。\n",
    "最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,2,1,2], p = 1\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= p &lt;= (nums.length)/2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-the-maximum-difference-of-pairs](https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-the-maximum-difference-of-pairs](https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,1,2,7,1,3]\\n2', '[4,2,1,2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        # Find the number of valid pairs by greedy approach\n",
    "        def countValidPairs(threshold):\n",
    "            index, count = 0, 0\n",
    "            while index < n - 1:\n",
    "                # If a valid pair is found, skip both numbers.\n",
    "                if nums[index + 1] - nums[index] <= threshold:\n",
    "                    count += 1\n",
    "                    index += 1\n",
    "                index += 1\n",
    "            return count\n",
    "        \n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            # If there are enough pairs, look for a smaller threshold.\n",
    "            # Otherwise, look for a larger threshold.\n",
    "            if countValidPairs(mid) >= p:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def valid(n):\n",
    "            cnt = 0\n",
    "            using = False\n",
    "            for i in range(1, len(nums)):\n",
    "                if nums[i] - nums[i-1] <= n and not using:\n",
    "                    using = True\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    using = False\n",
    "            return cnt >= p\n",
    "\n",
    "        lo, hi = 0, nums[-1] - nums[0] + 1\n",
    "\n",
    "        while lo < hi:\n",
    "            mi = (lo + hi) // 2\n",
    "            if not valid(mi):\n",
    "                lo = mi+1\n",
    "            else:\n",
    "                hi = mi\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        # 这一题二分的是差值\n",
    "        left, right = 0, nums[-1]-nums[0]\n",
    "\n",
    "        while left<=right:\n",
    "            mid = (left+right) // 2\n",
    "\n",
    "            cnt = 0 # 没有超过 mid 的数对的量\n",
    "            i=1\n",
    "            while i<len(nums):\n",
    "                if nums[i]-nums[i-1] <= mid:\n",
    "                    cnt += 1\n",
    "                    i += 1\n",
    "                i+=1\n",
    "            if cnt >= p:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        \n",
    "        def non_touch_min_k(nums, k):\n",
    "            \"\"\"寻找数组内不相信的第 k 小的值\"\"\"\n",
    "            m = max(nums)\n",
    "            n = min(nums)\n",
    "            while m >= n:\n",
    "                p = (m + n) // 2\n",
    "                count = 0\n",
    "                flag = True\n",
    "                for i in nums:\n",
    "                    if flag and i <= p:\n",
    "                        count += 1\n",
    "                        flag = False\n",
    "                    else:\n",
    "                        flag = True\n",
    "                if count >= k:\n",
    "                    m = p - 1\n",
    "                else:\n",
    "                    n = p + 1\n",
    "            return n\n",
    "\n",
    "        if not p:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        nsort = [0] * (n-1)\n",
    "        for i in range(1,n):\n",
    "            nsort[i-1] = nums[i] - nums[i-1]\n",
    "        return non_touch_min_k(nsort, p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums_len = len(nums)\n",
    "        nums.sort()\n",
    "        \n",
    "        max_v = nums[-1]-nums[0]\n",
    "        left = 0\n",
    "        right = max_v\n",
    "        def check(v):\n",
    "            dp =[0]*(nums_len+1)\n",
    "            for i in range(1, nums_len):\n",
    "                if nums[i]-nums[i-1] <= v:\n",
    "                    dp[i+1] = dp[i-1]+1\n",
    "                else:\n",
    "                    dp[i+1] = dp[i]\n",
    "            if dp[-1]>=p:\n",
    "                return True\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        while left<=right:\n",
    "            mid = left+(right-left)//2\n",
    "            if check(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        left,right=0,nums[0]-nums[-1]+1\n",
    "        def check(minV):\n",
    "            i,n=0,len(nums)\n",
    "            c=0\n",
    "            while i<n-1:\n",
    "                j=i+1\n",
    "                while j<n:\n",
    "                    if nums[i]-nums[j]<=minV:\n",
    "                        c+=1\n",
    "                        i=j+1\n",
    "                        break\n",
    "                    else:\n",
    "                        i=j\n",
    "                        break\n",
    "            return c>=p\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if not check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        left,right=0,nums[0]-nums[-1]+1\n",
    "        def check(minV):\n",
    "            i,n=0,len(nums)\n",
    "            c=0\n",
    "            while i<n-1:\n",
    "                j=i+1\n",
    "                while j<n:\n",
    "                    if nums[i]-nums[j]<=minV:\n",
    "                        c+=1\n",
    "                        i=j+1\n",
    "                        break\n",
    "                    else:\n",
    "                        i=j\n",
    "                        break\n",
    "            return c>=p\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if not check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = -1, nums[-1]-nums[0]+1\n",
    "        while left + 1 < right:\n",
    "            mid = left + right >> 1\n",
    "            if self.check(nums, mid, p) >= p:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "            # print(mid, left, right)\n",
    "        return right\n",
    "    \n",
    "    def check(self, nums, mid, p):\n",
    "        preused = False\n",
    "        cnt = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if preused:\n",
    "                preused = not preused\n",
    "                continue\n",
    "            if nums[i] - nums[i-1] <= mid:\n",
    "                cnt += 1\n",
    "                preused = True\n",
    "                if cnt >= p:break\n",
    "        # print(mid, cnt)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            i = 1\n",
    "            temp = p\n",
    "            while i < len(nums) and p:\n",
    "                if nums[i] - nums[i - 1] <= mid:\n",
    "                    i += 2\n",
    "                    p -= 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            if not p:\n",
    "                p = temp\n",
    "                right = mid\n",
    "            else:\n",
    "                p = temp\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        left,right=0,nums[0]-nums[-1]+1\n",
    "        def check(minV):\n",
    "            i,n=0,len(nums)\n",
    "            c=0\n",
    "            while i<n-1:\n",
    "                j=i+1\n",
    "                while j<n:\n",
    "                    if nums[i]-nums[j]<=minV:\n",
    "                        c+=1\n",
    "                        i=j+1\n",
    "                    else:\n",
    "                        i=j\n",
    "                    break\n",
    "            return c>=p\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if not check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def valid(n):\n",
    "            cnt = 0\n",
    "            using = False\n",
    "            for i in range(1, len(nums)):\n",
    "                if nums[i] - nums[i-1] <= n and not using:\n",
    "                    using = True\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    using = False\n",
    "            return cnt >= p\n",
    "\n",
    "        lo, hi = 0, 10**9+1\n",
    "\n",
    "        while lo < hi:\n",
    "            mi = (lo + hi) // 2\n",
    "            if not valid(mi):\n",
    "                lo = mi+1\n",
    "            else:\n",
    "                hi = mi\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def getCnt():\n",
    "            i = cnt = 0\n",
    "            while i < n-1:\n",
    "                if nums[i+1]-nums[i] <= m:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return cnt\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        l, r = 0, max(nums[i]-nums[i-1] for i in range(1, n))\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if getCnt()<p:\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(x: int):\n",
    "            i = 0\n",
    "            sum = 0\n",
    "            while i < n - 1:\n",
    "                if abs(nums[i + 1] - nums[i]) <= x:\n",
    "                    i += 2\n",
    "                    sum += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            return sum >= p\n",
    "        l, r = -1, max(nums) - min(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        def check(mx: int) -> bool:\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i+1] - nums[i] <= mx:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return cnt >= p\n",
    "\n",
    "        left, right = -1, max(nums) - min(nums) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def f(mx: int) -> int:\n",
    "            cnt = i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i + 1] - nums[i] <= mx:  # 都选\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:  # 不选 nums[i]\n",
    "                    i += 1\n",
    "            return cnt\n",
    "        return bisect_left(range(nums[-1] - nums[0]), p, key=f)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/solutions/2216315/er-fen-da-an-tan-xin-by-endlesscheng-dlxv/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(mid) -> bool:\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            while i < n-1:\n",
    "                if nums[i+1] - nums[i] <= mid:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return cnt >= p\n",
    "\n",
    "        left, right = 0, nums[-1]-nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left\n",
    "\n",
    "\n",
    "class Solution0:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def f(mx: int) -> int:\n",
    "            cnt = i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i + 1] - nums[i] <= mx:  # 都选\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:  # 不选 nums[i]\n",
    "                    i += 1\n",
    "            return cnt\n",
    "        return bisect_left(range(nums[-1] - nums[0]), p, key=f)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/solutions/2216315/er-fen-da-an-tan-xin-by-endlesscheng-dlxv/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        l, r = 0, nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        def check(x):\n",
    "            cnt = i = 0\n",
    "            while i < n - 1:\n",
    "                if nums[i + 1] - nums[i] <= x:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return cnt >= p\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        left = 0\n",
    "        right = max(nums) - min(nums)\n",
    "        nums.sort()\n",
    "        def check(tar):\n",
    "            i = 0\n",
    "\n",
    "            cnt = 0\n",
    "            while i + 1 < len(nums):\n",
    "                if nums[i + 1] - nums[i] <= tar:\n",
    "                    cnt += 1\n",
    "                    if cnt >= p:\n",
    "                        return True\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            \n",
    "            return cnt >= p\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(x,nums,p):\n",
    "    i = 0\n",
    "    ans = 0\n",
    "    while i < len(nums) - 1:\n",
    "        if abs(nums[i] - nums[i+1]) <= x:\n",
    "            ans += 1\n",
    "            i += 2\n",
    "        else:\n",
    "            i += 1\n",
    "    if ans >= p:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: list[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = 10 ** 9 + 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid,nums,p):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        print(l)\n",
    "        return l\n",
    "\n",
    "nums = [2,6,2,4,2,2,0,2]\n",
    "p = 4\n",
    "\n",
    "sol = Solution()\n",
    "sol.minimizeMax(nums,p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        def check(mx: int) -> bool:\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i+1] - nums[i] <= mx:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return cnt >= p\n",
    "\n",
    "        left, right = -1, nums[-1] - nums[0]\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        # def count_pair(gap):\n",
    "        #     i = res = 0\n",
    "        #     while i + 1 < len(nums):\n",
    "        #         if nums[i+1] - nums[i] <= gap:\n",
    "        #             i += 2 \n",
    "        #             res += 1\n",
    "        #         else:\n",
    "        #             i += 1\n",
    "        #     return res\n",
    "        \n",
    "        # nums.sort()\n",
    "        # l, r = 0, nums[-1]-nums[0]\n",
    "        # while l <= r:\n",
    "        #     mid = l + (r-l)//2\n",
    "        #     if count_pair(mid) >= p:\n",
    "        #         r = mid - 1\n",
    "        #     else:\n",
    "        #         l = mid + 1\n",
    "        # return l\n",
    "        \n",
    "        # -----------------------------------------\n",
    "        def count_pair(gap):\n",
    "            i = res = 0\n",
    "            while i + 1 < len(nums):\n",
    "                if nums[i+1] - nums[i] <= gap:\n",
    "                    i += 2 \n",
    "                    res += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            return res\n",
    "        \n",
    "        nums.sort()\n",
    "        return bisect.bisect_left(range(nums[-1]-nums[0]), p, key=count_pair)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        left,right=0,nums[0]-nums[-1]+1\n",
    "        def check(minV):\n",
    "            i,n=0,len(nums)\n",
    "            c=0\n",
    "            while i<n-1:\n",
    "                j=i+1\n",
    "                while j<n:\n",
    "                    if nums[i]-nums[j]<=minV:\n",
    "                        c+=1\n",
    "                        i=j+1\n",
    "                        break\n",
    "                    else:\n",
    "                        i=j\n",
    "                        break\n",
    "            return c>=p\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if not check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        \n",
    "        \n",
    "        def judge(ans, n):\n",
    "            cnt = 0\n",
    "            i=0\n",
    "            while i < len(nums)-1:\n",
    "                if nums[i+1]-nums[i]<=ans:\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    i+=1\n",
    "            return cnt>=n\n",
    "\n",
    "        left, right = 0, nums[-1]-nums[0]\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if judge(mid, p):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def check(self, nums: List[int], p: int, x: int):\n",
    "            n = len(nums)\n",
    "            i = 0\n",
    "            sum = 0\n",
    "            while i < n:\n",
    "                if i < n - 1 and abs(nums[i + 1] - nums[i]) <= x:\n",
    "                    i += 1\n",
    "                    sum += 1\n",
    "                i += 1\n",
    "            return sum >= p\n",
    "        \n",
    "        nums.sort()\n",
    "        l, r = -1, max(nums) - min(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, nums, p, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def check(k:int)->bool:\n",
    "            cnt=i=0\n",
    "            while i<len(nums)-1:\n",
    "                if nums[i+1]-nums[i]<=k:\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    i+=1\n",
    "            return cnt>=p\n",
    "                \n",
    "        \n",
    "        left,right=0,max(nums)\n",
    "        while left<=right:\n",
    "            mid=left+((right-left)>>1)\n",
    "            if check(mid):\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def check(nums: List[int], p: int, x: int):\n",
    "            n = len(nums)\n",
    "            i = 0\n",
    "            sum = 0\n",
    "            while i < n:\n",
    "                if i < n - 1 and abs(nums[i + 1] - nums[i]) <= x:\n",
    "                    i += 1\n",
    "                    sum += 1\n",
    "                i += 1\n",
    "            return sum >= p\n",
    "        \n",
    "        nums.sort()\n",
    "        l, r = -1, max(nums) - min(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(nums, p, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def check(lim):\n",
    "            pre, cnt = False, 0\n",
    "            for x, y in pairwise(nums):\n",
    "                if pre: pre = False\n",
    "                elif y - x <= lim:\n",
    "                    pre = True\n",
    "                    cnt += 1\n",
    "                    if cnt >= p: break\n",
    "            return cnt >= p\n",
    "\n",
    "        nums.sort()\n",
    "        return bisect_left(range(nums[-1] - nums[0]), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = nums[n-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if (self.check(nums, mid, p)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def check(self, nums, mid, p):\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < len(nums) - 1:\n",
    "            if nums[i + 1] - nums[i] <= mid:\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "            if cnt >= p:\n",
    "                return True\n",
    "            i += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l, r = 0, nums[-1] - nums[0]\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            while i < n-1 and cnt < p:\n",
    "                if nums[i+1] - nums[i] <= mid:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            if cnt == p:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = nums[-1] - nums[0]\n",
    "        while l <= r:\n",
    "            m = l + r >> 1\n",
    "            match = True\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if match:\n",
    "                    match = False\n",
    "                    continue\n",
    "                if nums[i] - nums[i - 1] <= m:\n",
    "                    cnt += 1\n",
    "                    match = True\n",
    "            if cnt >= p:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def dp(mx):\n",
    "            cnt=i=0\n",
    "            while i<len(nums)-1:\n",
    "                if nums[i+1]-nums[i]<=mx:\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    i+=1\n",
    "            return cnt\n",
    "        return bisect_left(range(nums[-1]-nums[0]),p,key=dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        # 判断能不能找到p个差值小于等与mid的下标对\n",
    "        def check(mid: int) -> bool:\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            # 贪心, 如果能够选nums[0], nums[1]直接选就行, 遍历一边数组就能求出最多数对个数\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i + 1] - nums[i] <= mid:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else: # 不选nums[i]\n",
    "                    i += 1\n",
    "            return cnt >= p\n",
    "            \n",
    "        l = 0\n",
    "        r = max(nums) - min(nums)\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums_len = len(nums)\n",
    "        nums.sort()\n",
    "        \n",
    "        max_v = nums[-1]-nums[0]\n",
    "        left = 0\n",
    "        right = max_v\n",
    "        def check(v):\n",
    "            f0 = 0\n",
    "            f1 =  0\n",
    "            for i in range(1, nums_len):\n",
    "                if nums[i]-nums[i-1] <= v:\n",
    "                    t = f1\n",
    "                    f1 = f0+1\n",
    "                    f0 = t\n",
    "                else:\n",
    "                    f0 = f1\n",
    "            if f1>=p:\n",
    "                return True\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        while left<=right:\n",
    "            mid = left+(right-left)//2\n",
    "            if check(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        '''\n",
    "        \n",
    "        最重要的是思维变换：\n",
    "        原始问题是【p 个下标对对应数值 最大差值 的 最小值 】\n",
    "        转变为\n",
    "        【设定最大差值的最小值为mx，p值应该为多少】。\n",
    "        在新问题中，mx约大，p值越小，极端情况下，mx就是nums中最大值与最小值的差，只需要p=1。\n",
    "        所以，我们是从一个类似于[...,3,2,2,1]的列表（这个队列与diff_list对应）中，\n",
    "        找到左起第一个满足条件的下标idx。\n",
    "        对应的，diff_list代表了nums数组可能存在的差值，上述第一个下标也就是range(nums[-1]-nums[0])中的取值\n",
    "        \n",
    "        '''\n",
    "\n",
    "        nums.sort()#排序之后，【最大差值的最小值】就是计算相邻元素差值\n",
    "\n",
    "        def fd(mx): #基于第一项的取值，即，max取range(nums[-1]-nums[0])中的一个值。基于此，计算所需p'值大小。在bisect_left中计算p'和p的大小，决定插入位置。\n",
    "\n",
    "            cnt=0\n",
    "            i=0\n",
    "            while i< len(nums)-1:\n",
    "                if nums[i+1]-nums[i]<=mx:#i和i+1都是用上了\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else:#i没有用上，i+1可以继续使用\n",
    "                    i+=1\n",
    "            return cnt\n",
    "\n",
    "        diff_list=range(nums[-1]-nums[0]) #可能的差值\n",
    "\n",
    "        return bisect_left(diff_list, p, key=fd) #返回range(nums[-1]-nums[0])中符合条件的第一个位置"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\r\n",
    "        # O(nlogn)\r\n",
    "        nums.sort()\r\n",
    "\r\n",
    "\r\n",
    "        def check(val:int) -> int:\r\n",
    "            # f(val) >= p\r\n",
    "            # 满足插值最大为val的数对的数量为p对\r\n",
    "            pair = 0\r\n",
    "\r\n",
    "            i = 1\r\n",
    "            # O(n)\r\n",
    "            while i < len(nums):\r\n",
    "                if nums[i] - nums[i-1] <= val:\r\n",
    "                    pair += 1\r\n",
    "                    i += 2\r\n",
    "                else:\r\n",
    "                    i += 1\r\n",
    "            \r\n",
    "            return pair\r\n",
    "\r\n",
    "        return bisect_left(range(nums[-1] - nums[0] + 1), p, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def check(max) -> bool:\n",
    "            cnt=i=0\n",
    "            while i<len(nums)-1:\n",
    "                if nums[i+1]-nums[i]<=max:\n",
    "                    i+=2\n",
    "                    cnt+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            return cnt>=p\n",
    "        left=0\n",
    "        right=nums[-1]-nums[0]\n",
    "        while left<=right:\n",
    "            mid=left+(right-left)//2\n",
    "            if check(mid):\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def check(mx:int):\n",
    "            n=len(nums)\n",
    "            pair=i=0\n",
    "            while i<n-1:\n",
    "                if nums[i+1]-nums[i]>mx:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    i+=2\n",
    "                    pair+=1\n",
    "            return pair>=p\n",
    "        left,right=-1,nums[-1]-nums[0]\n",
    "        while left+1<right:\n",
    "            mid=(right+left)//2\n",
    "            if check(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # 找相邻的比较好\n",
    "        l = -1\n",
    "        r = 10**9\n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) // 2\n",
    "            i = 1\n",
    "            c = 0\n",
    "            while i < n:\n",
    "                if nums[i] - nums[i - 1] <= mid:\n",
    "                    i += 2\n",
    "                    c += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            if c >= p:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def solve(x):\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            while i < len(nums) -1:\n",
    "                if nums[i+1]-nums[i] <= x:\n",
    "                    cnt += 1\n",
    "                    i+=2\n",
    "                else: i+=1\n",
    "            return cnt\n",
    "        \n",
    "        \n",
    "        return bisect_left(range(nums[-1] - nums[0]),p,key=solve)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "import sys\n",
    "# sys.setrecursionlimit(100000)\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l,r = 0,max(nums)\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            i,cnt = 1, 0\n",
    "            while i < n:\n",
    "                if nums[i] - nums[i-1] <= m:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            if cnt >= p:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def count_pair(gap):\n",
    "            i = res = 0\n",
    "            while i + 1 < len(nums):\n",
    "                if nums[i+1] - nums[i] <= gap:\n",
    "                    i += 2 \n",
    "                    res += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            return res\n",
    "        \n",
    "        nums.sort()\n",
    "        l, r = 0, nums[-1]-nums[0]\n",
    "        while l <= r:\n",
    "            mid = l + (r-l)//2\n",
    "            if count_pair(mid) >= p:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        left,right=0,nums[0]-nums[-1]+1\n",
    "        def check(minV):\n",
    "            i,n=0,len(nums)\n",
    "            c=0\n",
    "            while i<n-1:\n",
    "                j=i+1\n",
    "                while j<n:\n",
    "                    if nums[i]-nums[j]<=minV:\n",
    "                        c+=1\n",
    "                        i=j+1\n",
    "                    else:\n",
    "                        i=j\n",
    "                    break\n",
    "            return c>=p\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if not check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        if p == 0 or n == 1:\n",
    "            return 0 \n",
    "        nums.sort() \n",
    "\n",
    "        def check(k):\n",
    "            cnt = 0\n",
    "            vis = [0] * n\n",
    "            for i in range(1, n):\n",
    "                if not vis[i] and not vis[i-1]:\n",
    "                    if abs(nums[i]-nums[i-1]) <= k:\n",
    "                        vis[i] = vis[i-1] = 1\n",
    "                        cnt += 1\n",
    "            return cnt >= p \n",
    "        \n",
    "        l, r = 0, nums[-1] - nums[0]\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def check(x):\n",
    "            f0 = f1 = 0\n",
    "            for i in range(1, len(nums)):\n",
    "                if nums[i] - nums[i - 1] > x:\n",
    "                    f0 = f1\n",
    "                else:\n",
    "                    f0, f1 = f1, max(f0 + 1, f1)\n",
    "            return f1\n",
    "        \n",
    "        return bisect_left(range(nums[-1] - nums[0]), p, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # 设置差值的阈值为diff\n",
    "        def help(diff):\n",
    "            idx = 0\n",
    "            cnt = 0\n",
    "            while(idx < n-1):\n",
    "                if nums[idx+1] - nums[idx] <= diff:\n",
    "                    cnt += 1\n",
    "                    idx += 2\n",
    "                else:\n",
    "                    idx += 1\n",
    "            # 如果cnt >= p，说明阈值为diff的情况下，可以找到至少p组下标\n",
    "            return cnt >= p \n",
    "        \n",
    "        return bisect_right(range(nums[-1]-nums[0]+1), False, key = help)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        left = -1\n",
    "        right = max(nums) + 1\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        def check(mid):\n",
    "            cnt = i = 0\n",
    "            while i < n - 1:\n",
    "                if nums[i+1] - nums[i] <=mid:\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    i+=1\n",
    "            return cnt >=p\n",
    "\n",
    "        while left + 1< right:\n",
    "            mid = (left + right)>>1\n",
    "            if not check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return right\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        if p == 0:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def pair(m: int) -> int:\n",
    "            cnt = i = 0\n",
    "            while i < n - 1:\n",
    "                if nums[i + 1] - nums[i] <= m:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "                \n",
    "            return cnt\n",
    "\n",
    "        l, r = 0, nums[-1] - nums[0]\n",
    "        while l < r:\n",
    "            m = l + (r-l) // 2\n",
    "            c = pair(m)\n",
    "\n",
    "            if c < p:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m \n",
    "\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def solve(x):\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            while i < len(nums) -1:\n",
    "                if nums[i+1]-nums[i] <= x:\n",
    "                    cnt += 1\n",
    "                    i+=2\n",
    "                else: i+=1\n",
    "            return cnt\n",
    "        \n",
    "        \n",
    "        return bisect_left(range(nums[-1] - nums[0]),p,key=solve)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def f(mx: int) -> int:\n",
    "            cnt = i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i + 1] - nums[i] <= mx:  # 都选\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:  # 不选 nums[i]\n",
    "                    i += 1\n",
    "            return cnt\n",
    "        return bisect_left(range(nums[-1] - nums[0]), p, key=f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0] + 1\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            i = 1\n",
    "            cnt = 0\n",
    "            while i < n:\n",
    "                if nums[i] - nums[i - 1] <= mid:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            if cnt >= p:\n",
    "                right = mid\n",
    "                ans = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def isValid(thresh):\n",
    "            i, cnt = 0, 0\n",
    "            while i < len(nums) - 1:\n",
    "                if abs(nums[i] - nums[i+1]) <= thresh:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "                if cnt == p:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "\n",
    "        if p == 0:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        l = -1\n",
    "        r = 10 ** 9 + 1\n",
    "        while l + 1 != r:\n",
    "            mid = (l + r) // 2\n",
    "            if isValid(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def count(nums, target, p, n):\n",
    "            i = 1\n",
    "            count = 0\n",
    "            while i < n:\n",
    "                if nums[i] - nums[i - 1] <= target:\n",
    "                    count += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            \n",
    "            if count >= p:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = nums[-1]\n",
    "        n = len(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            condition = count(nums, mid, p, n)\n",
    "            if condition:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        if p == 0:\n",
    "            return 0\n",
    "\n",
    "        def is_valid(threshold):\n",
    "            i, cnt = 0, 0\n",
    "            while i < len(nums)-1:\n",
    "                if nums[i+1]-nums[i] <= threshold:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "                if cnt == p:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        nums.sort()\n",
    "        left, right = 0, max(nums)\n",
    "        res = max(nums)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if is_valid(mid):\n",
    "                res = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def check(self, nums: List[int], p: int, x: int):\n",
    "            n = len(nums)\n",
    "            i = 0\n",
    "            sum = 0\n",
    "            while i < n:\n",
    "                if i < n - 1 and abs(nums[i + 1] - nums[i]) <= x:\n",
    "                    i += 1\n",
    "                    sum += 1\n",
    "                i += 1\n",
    "            return sum >= p\n",
    "        \n",
    "        nums.sort()\n",
    "        l, r = -1, max(nums) - min(nums) + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, nums, p, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums_len = len(nums)\n",
    "        nums.sort()\n",
    "        \n",
    "        max_v = nums[-1]-nums[0]\n",
    "        left = 0\n",
    "        right = max_v\n",
    "        def check(v):\n",
    "            # dp =[0]*(nums_len+1)\n",
    "            # i-2\n",
    "            f0 = 0\n",
    "            # # i-1\n",
    "            f1 =  0\n",
    "            # # i\n",
    "            for i in range(1, nums_len):\n",
    "                if nums[i]-nums[i-1] <= v:\n",
    "                    t = f1\n",
    "                    f1 = f0+1\n",
    "                    f0 = t\n",
    "                    # f0 = t\n",
    "                else:\n",
    "                    # f2 = f1\n",
    "                    f0 = f1\n",
    "            print(f0,f1)\n",
    "            if f1>=p:\n",
    "                return True\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        while left<=right:\n",
    "            mid = left+(right-left)//2\n",
    "            if check(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # 设置差值的阈值为diff\n",
    "        def help(diff):\n",
    "            idx = 0\n",
    "            cnt = 0\n",
    "            while(idx < n-1):\n",
    "                if nums[idx+1] - nums[idx] <= diff:\n",
    "                    cnt += 1\n",
    "                    idx += 2\n",
    "                else:\n",
    "                    idx += 1\n",
    "            # 如果cnt >= p，说明阈值为diff的情况下，可以找到至少p组下标\n",
    "            return cnt >= p \n",
    "        \n",
    "        return bisect_left(range(nums[-1]-nums[0]+1), True, key = help)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        if p == 0:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            i = 0\n",
    "            while i < n-1:\n",
    "                if nums[i+1] - nums[i] <= k:\n",
    "                    count += 1\n",
    "                    i += 2\n",
    "                    if count >= p:\n",
    "                        return True\n",
    "                else:\n",
    "                    i += 1\n",
    "            return False\n",
    "        \n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right + 1) = True\n",
    "            if check(mid):\n",
    "                # 符合， mid应该缩小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        l, r = 0, nums[-1] - nums[0]\n",
    "        n = len(nums)\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            pre = 0\n",
    "            for i in range(1, n):\n",
    "                if i > pre and nums[i] - nums[pre] <= x:\n",
    "                    cnt += 1\n",
    "                    pre = i + 1\n",
    "                else:\n",
    "                    pre = i\n",
    "            return cnt >= p\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        def check(val):\n",
    "            cnt=0\n",
    "            i=0\n",
    "            while i<n-1:\n",
    "                if nums[i+1]-nums[i]<=val:\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    i+=1\n",
    "            return cnt\n",
    "        left=0\n",
    "        right=max(nums)\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid)<p:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        arr = []\n",
    "        l, r = 0, nums[-1] - nums[0]\n",
    "        \n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            i = 1\n",
    "            while i < n:\n",
    "                if nums[i] - nums[i-1] <= x:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i+=1\n",
    "            return cnt >= p \n",
    "\n",
    "        while l < r:\n",
    "            mid = ( l + r ) >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return l \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        l, r = 0, nums[-1] - nums[0]\n",
    "\n",
    "        def f(mx):\n",
    "            cnt = i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i + 1] - nums[i] <= mx: \n",
    "                    cnt += 1\n",
    "                    i += 1\n",
    "                i += 1\n",
    "            return cnt\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            cnt = f(mid)\n",
    "            if cnt >= p: r = mid\n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        def f(mx: int) -> int:\n",
    "            cnt = i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i + 1] - nums[i] <= mx:  # 都选\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:  # 不选 nums[i]\n",
    "                    i += 1\n",
    "            return cnt\n",
    "        return bisect_left(range(nums[-1] - nums[0]), p, key=f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        if p == 0 or len(nums)<2:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        # # 求差值\n",
    "        # n = len(nums)\n",
    "        # preDiff = [inf] * n\n",
    "        # for i in range(1, n):\n",
    "        #     preDiff[i] = nums[i] - nums[i-1]\n",
    "        # dp = preDiff\n",
    "        # # dp[i][j]，第i个位置作为第j个数对结尾的最小-最大差值\n",
    "        # for j in range(p-1):\n",
    "        #     newdp = [inf] * n\n",
    "        #     curmin = inf\n",
    "        #     for i in range(2*j+1, n-2):\n",
    "        #         curmin = min(curmin, dp[i])\n",
    "        #         newdp[i+2] = max(curmin, preDiff[i+2])\n",
    "        #     dp = newdp\n",
    "        # return min(dp)\n",
    "        def f(mx):\n",
    "            cnt = i = 0\n",
    "            while i < len(nums) - 1:\n",
    "                if nums[i+1] - nums[i] <= mx:\n",
    "                    cnt += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return cnt\n",
    "        \n",
    "        return bisect_left(range(nums[-1] - nums[0]), p, key=f)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            l = 0\n",
    "            while l < n-1:\n",
    "                if abs(nums[l] - nums[l+1]) <= x:\n",
    "                    res += 1\n",
    "                    l += 2\n",
    "                    if res >= p:\n",
    "                        return True\n",
    "                else:\n",
    "                    l += 1\n",
    "            return res >= p\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 0\n",
    "        nums.sort()\n",
    "        \n",
    "        left = 0\n",
    "        right = nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = (right - left) // 2 + left\n",
    "            if self.check(nums, p, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "    \n",
    "    def check(self, nums, p, mid):\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            if nums[i] - nums[i-1] <= mid:\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "            i += 1\n",
    "        return cnt >= p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        if(p == 0):\n",
    "            return 0\n",
    "        diff = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1):\n",
    "            diff.append(nums[i+1]-nums[i])\n",
    "        def check(x):\n",
    "            d0, d1 = 0, 1 if diff[0] <= x else 0\n",
    "            for i in range(1,len(diff)):\n",
    "                if(diff[i] <= x):\n",
    "                    d0, d1 = max(d0,d1), d0+1\n",
    "                else:\n",
    "                    d0, d1 = max(d0,d1), 0\n",
    "                if(max(d0,d1) >= p):\n",
    "                    return True\n",
    "            return max(d0,d1) >= p\n",
    "        left, right = min(diff), max(diff)\n",
    "        while(left <= right):\n",
    "            mid = (left + right)//2\n",
    "            if(check(mid)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        mx = nums[-1] - nums[0]\n",
    "        diff = [0] * (n - 1)\n",
    "        for i in range(n - 1):\n",
    "            diff[i] = nums[i + 1] - nums[i]\n",
    "        def check(mx: int) -> int:\n",
    "            ans = 0\n",
    "            i = 0\n",
    "            while i < n - 1:\n",
    "                if nums[i + 1] - nums[i] <= mx:\n",
    "                    ans += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return ans\n",
    "        return bisect_left(range(mx + 1), p, key = check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left,right = 0,nums[-1]-nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right)>>1\n",
    "            i = 1\n",
    "            cnt = 0\n",
    "            while i < n:\n",
    "                if nums[i] - nums[i-1] <= mid:\n",
    "                    cnt += 1\n",
    "                    if cnt == p: break\n",
    "                    i += 1\n",
    "                i += 1\n",
    "            if cnt >= p: right = mid-1\n",
    "            else: left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        if len(nums) == 1: return 0\n",
    "        nums.sort()\n",
    "        gaps = [nums[i] - nums[i - 1] for i in range(1, len(nums))]\n",
    "        \n",
    "        def check(gap):\n",
    "            i, count = 0, 0\n",
    "            while i < len(gaps):\n",
    "                if gaps[i] <= gap:\n",
    "                    count += 1\n",
    "                    i += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "                if count >= p:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        l, r = 0, max(gaps)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        l,r = -1, nums[-1]-nums[0]\n",
    "        while l+1 < r:\n",
    "            mid = (l+r)>>1\n",
    "            cnt = 0\n",
    "            i=0\n",
    "            while i <n-1:\n",
    "                if nums[i+1]-nums[i]<=mid:\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else:\n",
    "                    i+=1\n",
    "            print(cnt)\n",
    "            if cnt>=p:\n",
    "                r = mid\n",
    "            else:\n",
    "                l =mid   \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        diff = list()\n",
    "        for i in range(1, n):\n",
    "            diff.append(nums[i] - nums[i - 1])\n",
    "        \n",
    "        def check(a):\n",
    "            cnt = 0\n",
    "            flag = False\n",
    "            for i, nu in enumerate(diff):\n",
    "                if not flag and nu <= a:\n",
    "                    cnt += 1\n",
    "                    flag = True\n",
    "                else:\n",
    "                    flag = False\n",
    "            return cnt >= p             \n",
    "        \n",
    "        i = 0\n",
    "        j = 10 ** 9\n",
    "        while i < j:\n",
    "            mid = (i + j) >> 1\n",
    "            if check(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        return i\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        left,right=0,nums[-1]-nums[0]+1\n",
    "        print(left,right)\n",
    "        ans=0\n",
    "        while left<right :\n",
    "            dis=(left+right)//2\n",
    "            cnt=0\n",
    "            i=1\n",
    "            while i<n :\n",
    "                if nums[i]-nums[i-1]<=dis :\n",
    "                    cnt+=1\n",
    "                    i+=2\n",
    "                else :\n",
    "                    i+=1\n",
    "            if cnt>=p :\n",
    "                right=dis\n",
    "                ans=dis\n",
    "            else :\n",
    "                left=dis+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        if p == 0:\n",
    "            return 0\n",
    "\n",
    "        def check(x: int, differences: List[int]) -> bool:\n",
    "            count, visited = 0, False\n",
    "\n",
    "            for difference in differences:\n",
    "                if visited is False and difference <= x:\n",
    "                    count += 1\n",
    "                    visited = True\n",
    "                else:\n",
    "                    visited = False\n",
    "\n",
    "                if count >= p:\n",
    "                    return True\n",
    "\n",
    "            return count >= p\n",
    "\n",
    "        sorted_nums = sorted(nums)  # ascending\n",
    "        diffs = []\n",
    "\n",
    "        for i in range(1, len(sorted_nums)):\n",
    "            diffs.append(sorted_nums[i] - sorted_nums[i - 1])\n",
    "\n",
    "        left, right = min(diffs), max(diffs)\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if check(middle, diffs):\n",
    "                right = middle - 1\n",
    "            else:\n",
    "                left = middle + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeMax(self, nums: List[int], p: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "\n",
    "        different=[0 for i in range(len(nums)-1) ]\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            different[i]=nums[i+1]-nums[i]\n",
    "\n",
    "        print(nums)\n",
    "        print(different)\n",
    "\n",
    "        different1=[different[i] for i in range(len(different)) if i%2==0]\n",
    "        different2=[different[i] for i in range(len(different)) if i%2!=0]\n",
    "\n",
    "        max_=[1e9]\n",
    "        #print(different)\n",
    "\n",
    "        def dfs(different,index,max_,local_max_,now_p,p,last_index):\n",
    "            \n",
    "            if(now_p==p):\n",
    "                max_[0]=min(max_[0],local_max_)\n",
    "                #print(\"max\",max_)\n",
    "                return \n",
    "\n",
    "            if(index>=len(different)):\n",
    "                return \n",
    "\n",
    "            dfs(different,index+1,max_,local_max_,now_p,p,last_index)\n",
    "            #if(index>last_index+1):\n",
    "            dfs(different,index+2,max_,max(local_max_,different[index]),now_p+1,p,index)\n",
    "\n",
    "        #dfs(different,0,max_,0,0,p,-2)\n",
    "\n",
    "        #f=[[1e9 for i in range(len(different))]\n",
    "        \n",
    "        #f=[[1e9 for i in range(p+1)] for j in range(len(different))]\n",
    "\n",
    "        # for i in range(len(different)):\n",
    "        #     f[i][1]=different[i]\n",
    "        #     for j in range(0,i):\n",
    "\n",
    "       \n",
    "\n",
    "        left=0\n",
    "\n",
    "        right=max(nums)\n",
    "\n",
    "        def judge(mid,different,p):\n",
    "            d=[x>mid for x in different]\n",
    "\n",
    "            last_i=-2\n",
    "            cnt=0\n",
    "            for i in range(len(d)):\n",
    "                if(d[i]==False and i>last_i+1):\n",
    "                    cnt+=1\n",
    "                    last_i=i \n",
    "                else:\n",
    "                    pass\n",
    "            #del d \n",
    "            return cnt>=p\n",
    "\n",
    "\n",
    "        while(left<right):\n",
    "            mid=left+(right-left)//2\n",
    "\n",
    "            if(judge(mid,different,p)):\n",
    "                right=mid \n",
    "            else:\n",
    "                left=mid+1\n",
    "            \n",
    "          \n",
    "        return left\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
